package String;

import java.util.*;

/**
 * @Classname JZ38字符串的排列
 * @Description TODO
 * @Date 2022/12/10 14:01
 * @Created by xjl
 */
public class JZ38字符串的排列 {
    List<String> result;
    boolean[] vis;

    public String[] permutation(String s) {
        int n = s.length();
        result = new ArrayList<String>();
        vis = new boolean[n];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        StringBuffer perm = new StringBuffer();
        dfs(arr, 0, n, perm);
        int size = result.size();
        String[] recArr = new String[size];
        for (int i = 0; i < size; i++) {
            recArr[i] = result.get(i);
        }
        return recArr;
    }

    public void dfs(char[] arr, int i, int n, StringBuffer sb) {
        if (i == n) {
            result.add(sb.toString());
            return;
        }
        for (int j = 0; j < n; j++) {
            // 如果是数据有相同的 那也会
            if (vis[j] || (j > 0 && !vis[j - 1] && arr[j - 1] == arr[j])) {
                continue;
            }
            vis[j] = true;
            sb.append(arr[j]);
            dfs(arr, i + 1, n, sb);
            sb.deleteCharAt(sb.length() - 1);
            vis[j] = false;
        }
    }
}
